The present invention relates to an arithmetic operation method and an arithmetic operation device, and more particularly an arithmetic operation method or an arithmetic operation device thereof for exponentiation or scalar multiplication.
Conventionally, in the case of using an encryption method such as a public-key cryptography, encrypted data has been generated by multiplying plain text data to be encrypted and an encryption key. And decryption of encrypted data has been performed by multiplying encrypted data and a decryption key.
In this case, plain text data and an encryption key, and encrypted data and a decryption key are respectively elements of an extension field, and the multiplication is performed over the extension field.
For example, in the Elgamal cryptography, an extension field Fpm of characteristic p and extension degree m is used. Particularly, in order to ensure security of encrypted data against decryption by a third party, the key length is set to be 2000 bits. In this case, it is necessary to perform exponentiation operation such as An using 2000 bit positive integer n<pm with respect to a non zero element A of the extension field.
In addition, generally, in order to construct an extension field Fpm, an irreducible polynomial f(x) of degree m over an extension field Fp is prepared and letting the zero thereof be ωεFpm, the following basis is prepared.{1,ω,ω2, . . . ,ωm−1}
This basis is particularly called polynomial basis and any element AεFpm is represented by the following expression.A=a0+a1ω+ . . . +am−1ωm−1 
That is, a vector representation of an element A becomes vA=(a0, a1, . . . , am−1).
Further, when a set of conjugate elements of ω with respect to Fp shown below forms a basis, the set is called a normal basis.{ω,ωp,ωp2, . . . ,ωpm−1}  [E16]
This normal basis is, as shown below, a basis suitable for the Frobenius map and considering any element A of Fpm as follows,A=a0ω+a1ωp+ . . . +am−1ωpm−1=(a0,a1, . . . ,am−1)  [E17]
The Frobenius map is given as follows.A→Ap Ap=a0ωp+a1ωp2+ . . . +am−2ωpm−1+am−1ω=(am−1,a0, . . . ,am−2)  [E18]
That is, when using the normal basis, it is found out that the Frobenius map does not require mathematical computation. Hereinafter in the present invention, i-th iterate of the Frobenius map is assumed to be denoted as follows.φi(A)=Api  [E19]
Exponentiation operations significantly affect the time required for arithmetic operations for encryption and decryption, and speeding up exponentiation operations leads to speeding up arithmetic operations for encryption and decryption. And hence, there has been proposed various methods to perform exponentiation operations at high speed.
As one of the methods, there has been known a binary method (see non-patent document 1, for example.). For example, in the case of performing an arithmetic operation “55P” (P is a point on an elliptic curve.) of a scalar multiplication in an elliptic curve function, since “55” is equivalent to a binary number “110111”, the arithmetic operation is performed by making use of “55P” being represented as,(110111)2P=2(2(22(2P+P)+P)+P)+P , and hence, the number of operations is reduced thus speeding up the arithmetic operation. Here, “( )2” denotes a binary representation. In this binary method, Flr(log2(n)) times of doublings and Flr(log2(n))/2 times of multiplications are necessary in average.
In addition, there has been proposed a method called a window method (see non-patent document 2, for example.). In the window method, in the case of assuming a window size to be 3, for example, respective components of A2,A3,A4,A5, A6,A7 are preliminarily prepared with respect to an element A. In the case of performing an arithmetic operation A318, by making use of “318” being equivalent to a binary number “100111110”, A318 is represented as,
                              A          318                =                              A                                          (                100111110                )                            2                                =                                                    {                                                                            (                                              A                                                                              (                            100                            )                                                    2                                                                    )                                                              2                      3                                                        ⁢                                      (                                          A                                                                        (                          111                          )                                                2                                                              )                                                  }                                            2                3                                      ⁢                          A                                                (                  110                  )                                2                                                                        [        E20        ]            And since (100)2=4, (11)2=7, (110)2=6, the arithmetic operation is performed using components of A4,A6,A7. Here, excluding a computation for preparing each component, in the window method, Flr(log2n)−w times of doublings and Flr(log2n/w) times of multiplications are necessary.    Non-patent document 1: H. Cohen and G. Frey et al, “Handbook of elliptic and hyperelliptic curve cryptography”, published by Chapman & Hall/CRC, 2006, p. 146.    Non-patent document 2: H. Cohen and G. Frey et al, “Handbook of elliptic and hyperelliptic curve cryptography”, published by Chapman & Hall/CRC, 2006, p. 149.    Non-patent document 3: T. Yoshida, H. Kato, K. Nekado, Y. Nogami and Y. Morikawa, “Consideration on Efficient Exponentiation in Extension Field for Pairing-based Cryptography”, Tech. Rep. of IEICE, ISEC vol. 108, no. 162, pp. 101-108, 2008.